package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 508. 出现次数最多的子树元素和
 * @author feizns
 * @since 2020/3/10
 */
public class FindFrequentTreeSum {

    public static void main(String[] args) {

        List<Integer> ret = new LinkedList<>();
        ret.add(1);
        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("hello.txt"))) {
            oos.writeObject(ret);
        } catch (IOException e) {

        }

        List<Integer> w = null;
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream("hello.txt"))) {
            w = (List<Integer>) ois.readObject();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }

        System.out.println(w); // [1]

    }

    static TreeMap<Integer, Integer> MAP = new TreeMap<>();

    public static int[] findFrequentTreeSum(TreeNode root) {
        treeSum(root);
        List<Integer> ret = null;
        Integer max = null;
        for (Map.Entry<Integer, Integer> entry : MAP.entrySet()) {
            Integer val = entry.getValue();
            if ( max == null || max < val ) {
                max = val;
                ret = new LinkedList<>();
            }
            if ( max == val )
                ret.add(entry.getKey());
        }
        return ret != null ? ret.stream().mapToInt(Integer::intValue).toArray() : new int[]{ };
    }

    private static int treeSum(TreeNode root) {
        if ( root != null ) {
            int l = treeSum(root.left);
            int r = treeSum(root.right);
            int e = l + r + root.val;
            Integer val = MAP.get(e);
            if ( val == null )
                val = 0;
            MAP.put(e, val + 1);
            return e;
        }
        return 0;
    }



}
